# 106. 从中序与后序遍历序列构造二叉树
# 给定两个整数数组 inorder 和  postorder ，其中 inorder 是二叉树的中序遍历， postorder是同一棵树的后序遍历，请你构造并返回这颗二叉树 。

# 示例
# 1:输入：inorder = [9, 3, 15, 20, 7], postorder = [9, 15, 7, 20, 3] 输出：[3, 9, 20, null, null, 15, 7]
# 示例 2:
# 输入：inorder = [-1], postorder = [-1]
# 输出：[-1]
#
# 提示:
# 1 <= inorder.length <= 3000postorder.length == inorder.length -3000 <= inorder[i], postorder[i] <= 3000
# inorder 和 postorder 都由不同的值组成 postorder 中每一个值都在inorder 中
# inorder 保证是树的中序遍历
# postorder 保证是树的后序遍历

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution(object):
    def buildTree(self, inorder, postorder):
        """
        :type inorder: List[int]
        :type postorder: List[int]
        :rtype: TreeNode
        """

        if len(inorder) != len(postorder):
            return None

        in_order_set = set(inorder)
        for postorder_item in postorder:
            if postorder_item not in in_order_set:
                return None
        root = self.iterateBuildTree(inorder, postorder)
        return root

    def iterateBuildTree(self, inorder, postorder):

        if len(postorder) == 0:
            return None

        root_node = TreeNode(postorder[-1])

        inorder_root_idx = 0
        for inorder_root_idx in range(0, len(inorder)):
            if inorder[inorder_root_idx] == postorder[-1]:
                break

        inorder_left_nodes = []
        inorder_right_nodes = []
        if inorder_root_idx > 0:
            inorder_left_nodes = inorder[0:inorder_root_idx]
        if inorder_root_idx + 1 < len(inorder):
            inorder_right_nodes = inorder[inorder_root_idx + 1:len(inorder)]

        postorder_left_nodes = []
        postorder_right_nodes = []
        if len(inorder_left_nodes) > 0:
            postorder_left_nodes = postorder[0:len(inorder_left_nodes)]
        if len(inorder_right_nodes) > 0:
            postorder_right_nodes = postorder[len(inorder_left_nodes):len(inorder) - 1]

        root_node.left = self.iterateBuildTree(inorder_left_nodes, postorder_left_nodes)
        root_node.right = self.iterateBuildTree(inorder_right_nodes, postorder_right_nodes)
        return root_node
